package middle;

import java.util.ArrayList;
import java.util.List;

public class Solution_5 {

    public String longestPalindrome(String s) {
        int max_length = 1, begin = 0, end = 0;
        char[] chars = s.toCharArray();
        List<Integer>[] array = new List[chars.length];
        array[0] = new ArrayList();
        array[0].add(0);
        for (int i = 1; i < chars.length; i++) {
            List<Integer> pres = array[i - 1];
            List<Integer> list = new ArrayList<>();
            list.add(i);
            if (chars[i - 1] == chars[i]) {
                list.add(i - 1);
                if (2 > max_length) {
                    max_length = 2;
                    begin = i - 1;
                    end = i;
                }
            }
            for (int j = 0; j < pres.size(); j++) {
                Integer pre_index = pres.get(j);
                if (pre_index > 0 && chars[pre_index - 1] == chars[i]) {
                    list.add(pre_index - 1);
                    if (i - pre_index + 2 > max_length) {
                        max_length = i - pre_index + 2;
                        begin = pre_index - 1;
                        end = i;
                    }
                }
            }
            array[i] = list;
        }
        return new String(chars, begin, end - begin + 1);
    }

    /*public String longestPalindrome(String s) {
        char[] chars = s.toCharArray();
        return dps(chars, 0, chars.length - 1);
    }

    private String dps(char[] chars, int begin, int end) {
        int i = begin, j = end;
        while (i < j) {
            if (chars[i] == chars[j]) {
                i++;
                j--;
            } else {
                break;
            }
        }
        if (i < j) {
            String dps_left = dps(chars, begin + 1, end);
            String dps_right = dps(chars, begin, end - 1);
            return dps_left.length() >= dps_right.length() ? dps_left : dps_right;
        }
        return new String(chars, begin, end - begin + 1);
    }*/

    public static void main(String[] args) {
        Solution_5 model = new Solution_5();
        System.out.println(model.longestPalindrome("babaddtattarrattatddetartrateedredividerb"));
        //        System.out.println(model.longestPalindrome("ccc"));
        //        System.out.println(model.longestPalindrome("babad"));
        //        System.out.println(model.longestPalindrome("cbbd"));
        //        System.out.println(model.longestPalindrome("a"));
        //        System.out.println(model.longestPalindrome("ac"));
    }
}
